package 二叉树.树基本知识与重建;

import java.util.ArrayList;

/**
 * Created by Administrator on 2017/8/4.
 */

//二叉树的题目普遍可以用递归和迭代的方式来解(判断左右孩子是否为空)
public class TreeNodeTest{
    //二叉树最多有两个子分支
/*    static class TreeNode {//静态内部类(设置为静态，是因为需要被main方法访问到)
        int val;
        //左孩子
        TreeNode left;
        //右孩子
        TreeNode right;
        //有参构造，给节点赋值
        public TreeNode(int root){ val=root; }
        public TreeNode(){}
    }*/

    public static void main(String[] args) {
        //1、生成二叉树
        TreeNode treeNode = createTreeNode();
        //2、二叉树遍历的三种方式：前序遍历，中序遍历，后序遍历
        preorderTraversal(treeNode); //前序遍历
        System.out.println();
        midorderTraversal(treeNode);//中序遍历
        System.out.println();
        lastorderTraversal(treeNode);//后序遍历
        System.out.println();
        //3、二叉树的最大/小深度
        // 求二叉树的最大深度
        int maxDepth=maxDepth(treeNode);
        System.out.println("最大深度:"+maxDepth);
        //求二叉树的最小深度(难点)
        int minDepth=minDepth(treeNode);
        System.out.println("最小深度:"+minDepth);
        //4、求二叉树的节点/叶子节点数目
        //求二叉树的节点数目
        int nodeNum=nodeNum(treeNode);
        System.out.println("节点数目："+nodeNum);
        //求二叉树的叶子节点数目
        int leafNodeNum=leafNodeNum(treeNode);
        System.out.println("叶子节点数目："+leafNodeNum);
        //5、求二叉树中第k层节点的个数
        int kLevelNodeNum = kLevelNodeNum(treeNode, 3);
        System.out.println("第k层节点的个数:"+kLevelNodeNum);
        //6、判断二叉树是否是平衡二叉树
        boolean isBalanceBinaryTree = isBalanceBinaryTree(treeNode);
        System.out.println("是否是平衡二叉树:"+isBalanceBinaryTree);

        //7、从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行
        System.out.println("按层打印二叉树："+print(treeNode));
    }

    //生成二叉树(最笨的方法)
    //分为对象创建和赋值
    public static TreeNode createTreeNode(){
        TreeNode treeNode = new TreeNode();
        treeNode.val=1;
        treeNode.left=new TreeNode();
        treeNode.left.val=2;
        treeNode.right=new TreeNode();
        treeNode.right.val=3;
        treeNode.left.left=new TreeNode();
        treeNode.left.left.val=4;
        treeNode.left.right=new TreeNode();
        treeNode.left.right.val=5;
/*        TreeNode root=new TreeNode(1);
        TreeNode root21=new TreeNode(2);
        TreeNode root22=new TreeNode(3);
        TreeNode root31=new TreeNode(4);
        TreeNode root32=new TreeNode(5);
        root.left=root21;
        root.right=root22;
        root21.left=root31;
        root21.right=root32;*/
        return treeNode;
    }

    //--------------------------------------------------------------------------------------------------
    //二叉树遍历的三种方式：前序遍历，中序遍历，后序遍历
    //前序遍历(规则：先打印中间节点的值，再依次打印左孩子和右孩子)
    public static void preorderTraversal(TreeNode treeNode){
        if(treeNode!=null){
            System.out.print(treeNode.val+","); //前序
            preorderTraversal(treeNode.left);
            preorderTraversal(treeNode.right);
        }
    }
    //中序遍历(规则：先打印最左边节点的值，再依次打印中间节点和右孩子)
    public static void midorderTraversal(TreeNode treeNode){
        if(treeNode!=null){
            midorderTraversal(treeNode.left);
            System.out.print(treeNode.val+","); //中序
            midorderTraversal(treeNode.right);
        }
    }
    //后序遍历(规则：先打印最左边节点的值，再依次打印右孩子和中间节点)
    public static void lastorderTraversal(TreeNode treeNode){
        if(treeNode!=null){
            lastorderTraversal(treeNode.left);
            lastorderTraversal(treeNode.right);
            System.out.print(treeNode.val+","); //后序
        }
    }
    //--------------------------------------------------------------------------------------------------
    //求二叉树的最大深度
    public static int maxDepth(TreeNode treeNode) {
        if(treeNode==null){
            return 0;
        }
        int left=maxDepth(treeNode.left);
        int right=maxDepth(treeNode.right);
        return Math.max(left,right)+1;
    }
    //求二叉树的最小深度(重难点)
    //不能按照比较最大深度的方式获得最小深度
    public static int minDepth(TreeNode treeNode){
        if(treeNode==null){ //判断是不是空的二叉树
            return 0;
        }
        return getMin(treeNode);
    }
    private static int getMin(TreeNode treeNode) {
        if(treeNode==null){ //当前节点为空时(有一个孩子为空时)，默认返回节点深度都最大整数(为了便于比较出一个较大深的节点)
            return Integer.MAX_VALUE;
        }
        if(treeNode.left==null&&treeNode.right==null){ //当前节点的左右节点都为空时，返回1，即当前节点孤单，只有一个
            return 1;
        }
        return Math.min(getMin(treeNode.left),getMin(treeNode.right))+1;//min表示从上往下累积最小深度，+1表示当前节点
    }

    //求二叉树的节点数目
    public static int nodeNum(TreeNode treeNode){
        if(treeNode==null){return 0;}
        return nodeNum(treeNode.left)+nodeNum(treeNode.right)+1; //左边节点+右边节点+中间节点
    }

    //求二叉树的叶子节点数目
    public static int leafNodeNum(TreeNode treeNode){
        if(treeNode==null){return 0;}
        if(treeNode.left==null&&treeNode.right==null){ //叶子节点：孤家寡人一个
            return 1;
        }
        return nodeNum(treeNode.left)+nodeNum(treeNode.right); //左边节点+右边节点
    }

    //求二叉树中第k层节点的个数
    public static int kLevelNodeNum(TreeNode treeNode,int kLevel){
        if(treeNode==null||kLevel<1){//空节点或超过层数，都返回0
            return 0;
        }
        if(kLevel==1){ //相当于逆序判断是否到达第k层
            return 1;
        }
        int leftNum=kLevelNodeNum(treeNode.left,kLevel-1);
        int rightNum=kLevelNodeNum(treeNode.right,kLevel-1);
        return leftNum+rightNum;//第k层左边节点+第k层右边节点
    }

    //判断二叉树是否是平衡二叉树
    //平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
    public static boolean isBalanceBinaryTree(TreeNode treeNode){
        if(treeNode==null){return true;}
        int leftDepth=maxDepth(treeNode.left);
        int rightDepth=maxDepth(treeNode.right);
        if(Math.abs(leftDepth-rightDepth)>1){return false;}
        return true;
    }

//   从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
    //关键技术点：按层创建集合(同一层直接用)，层=集合长度，第N层数据=集合第N-1个元素
    public static ArrayList<ArrayList<Integer>> print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        depth(pRoot,1,arrayLists);//二叉树.二叉树，第N层，按要求排列的集合(集合的长度代表了多少层)
        return arrayLists;
    }
    private static void depth(TreeNode pRoot, int depth, ArrayList<ArrayList<Integer>> arrayLists) {
        if(pRoot==null) return; //空节点直接返回。终止条件。
        if(depth>arrayLists.size()) arrayLists.add(new ArrayList<Integer>());//深度增加了，就创建一个新的集合来接收
        arrayLists.get(depth-1).add(pRoot.val); //易错：集合中第0个，代表第1层

        depth(pRoot.left,depth+1,arrayLists);//左孩子
        depth(pRoot.right,depth+1,arrayLists);//右孩子
    }

}
